package org.example.myleet.p473;

import java.util.HashSet;

public class Solution {

    /**
     * 记忆化搜索
     */
    private final HashSet<Integer> existence = new HashSet<>();

    public boolean makesquare(int[] matchsticks) {
        existence.clear();
        int sumOfLen = 0;
        for (int matchStick : matchsticks) {
            sumOfLen += matchStick;
        }
        if (sumOfLen % 4 != 0) {
            //不能被4整除，不可能找到正方形
            return false;
        }
        //正方形边长
        int edgeLen = sumOfLen / 4;
        return backtrack(matchsticks, 0, 0, 1, edgeLen);
    }

    private boolean backtrack(int[] matchsticks, int status, int sum, int edgeNum, int edgeLen) {
        if (edgeNum == 5 && sum == 0) {
            //找到一种符合正方形摆法的结果，OK
            return true;
        }
        for (int i = 0; i < matchsticks.length; ++i) {
            int bits = 1 << i;
            if ((status & bits) == 0) {
                int newSum = sum + matchsticks[i];
                if (edgeLen < newSum) {
                    //newSum边长大于目标边长，当前组合行不通，剪枝
                    continue;
                }
                int newEdgeNum = edgeNum;
                if (edgeLen == newSum) {
                    //找到一条边的组合，修改状态，开始下一条边的搜索
                    ++newEdgeNum;
                    newSum = 0;
                }
                int newStatus = status | bits;
                if (existence.contains(newStatus)) {
                    //记忆化搜索
                    //当前组合已出现过且行不通，剪枝
                    continue;
                }
                if (backtrack(matchsticks, newStatus, newSum, newEdgeNum, edgeLen)) {
                    //找到其中一种组合，OK
                    return true;
                } else {
                    //当前组合行不通，保存到记忆中
                    existence.add(newStatus);
                }
            }
        }
        //当前组合行不通，保存到记忆中
        existence.add(status);
        return false;
    }
}
